package algorithm.sort;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @author LiDong
 * @version 1.0.0
 * @createTime 2/22/2022 10:06 PM
 */
public class QuickSort {

    private static final Logger logger = LoggerFactory.getLogger(QuickSort.class);


    @Test
    public void test() {
        int[] arr = {1, 5, 3, 4, 2, 6};
        quickSort(arr, 0, 5);
    }

    private void quickSort(int[] arr, int begin, int end) {
        if (begin < end) {
            int i = begin;
            int j = end;
            // 基准元素
            int key = arr[begin];
            while (i < j) {
                // 从右向左找小于基准元素 z 的值填在 arr[i]
                while (i < j && arr[j] > key) {
                    j--;
                }
                if (i < j) {
                    // 将 arr[j] 填到 arr[i] 上，arr[j] 就空了下来
                    arr[i] = arr[j];
                    // 从左向右找
                }
                // 从左向右找大于或等于 x 的数来填 arr[j]
                while (i < j && arr[i] < key) {
                    i++;
                }
                if (i < j) {
                    arr[j] = arr[i];
                    j--;
                }

            }
            //退出时，i等于j。将x填到这个坑中。
            arr[i] = key;
            quickSort(arr, begin, i - 1);
            quickSort(arr, i + 1, end);
        }
    }


}
